#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

const int N = 1e6 + 10, INF = 0x3f3f3f3f;

int n;
int a[N], f[N];  // a[]：转换后的数组，f[]：用于LIS的dp数组

void solve()
{
    cin >> n;

    for (int i = 1;i <= n;i++) cin >> a[i];

    // LIS（最长上升子序列）核心逻辑
    int tt = 0;  // tt 记录当前 LIS 的长度
    for (int i = 1; i <= n; i++) {
        int l = 0, r = tt;
        // 在 f[0..tt) 中二分查找第一个比 a[i] 大的位置
        // f[] 中维护的是当前 LIS 的末尾值，越小越好（贪心）
        while (l < r) {
            int mid = (l + r) >> 1;
            if (f[mid] > a[i]) r = mid;   // 有更小的末尾可替换，向左找
            else l = mid + 1;             // 否则向右扩展
        }
        // 更新 LIS 长度
        tt = max(tt, l + 1);
        // 更新末尾值
        f[l] = a[i];
    }

    // 输出 LIS 长度，即两个数组的最长公共子序列长度
    cout << tt;
}

signed main()
{
#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    std::istringstream in(R"()");
    std::cin.rdbuf(in.rdbuf());
#endif
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve();
    }
}
